|
In some tasks of integrated circuit layout design a necessity arises to optimize placement of non-overlapping objects in the plane. In general this problem is extremely hard, and to tackle it with computer algorithms, certain assumptions are made about admissible placements and about operations allowed in placement modifications. Constraint graphs capture the restrictions of relative movements of the objects placed in the plane. These graphs, while sharing common idea, have different definition, depending on a particular design task or its model. ==Floorplanning== In floorplanning, the model of a floorplan of an integrated circuit is a set of isothetic rectangles called "blocks" within a larger rectangle called "boundary" (e.g., "chip boundary", "cell boundary"). A possible definition of constraint graphs is a s follows. The constraint graph for a given floorplan is a directed graph with vertex set being the set of floorplan blocks and there is an edge from block b1 to b2 (called horizontal constraint), if b1 is completely to the left of b2 and there is an edge from block b1 to b2 (called vertical constraint), if b1 is completely below b2. If only horizontal constraints are considered, one obtains the horizontal constraint graph. If only vertical constraints are considered, one obtains the vertical constraint graph. Under this definition, the constraint graph can have as many as edges, where ''n'' is the number of blocks. Therefore other, less dense constraint graphs are considered. The horizontal visibility graph is a horizontal constraint graph in which the horizontal constraint between two blocks exists only if there is a horizontal line segment which connects the two blocks and does not intersect any other blocks. In other words, one block is a potential "immediate obstacle" for moving another one horizontally. The vertical visibility graph is defined in a similar way. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Constraint graph (layout)」の詳細全文を読む スポンサード リンク
|